/**
 * 打牌的时候，我们每拿到一张牌，就会选择性把牌插入到合适的位置，效果就是它前面的数字比它小，它后面的数字比它大。
 * 插入排序也是这样，排序时从第二个数开始作为基数，和它前面的数字比较
 * 如果基数比前面的数字小，两个值交换一下，它就挪到前面，再继续和前面的比较，直到遇到一个前面的数字比它小（它比前面的数字大），就停止。
 * 如果直接遇到比前面的大的情况，就放下这个数，选择后一个数作为基数继续开始比较。
 */
package com.test.sort;

import java.util.Arrays;
public class InsertionSort {

    public static void main(String[] args) {
        int[] a = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        for (int i = 1; i < a.length; i++) {  //排序循环，从第二个元素开始作为基数，每一个元素一轮排序，最后一个元素结束。第一个元素不参与排序
            if (a[i] < a[i-1]) {  //每轮开始后，抽出的这个元素基数，如果比前面的数字小，则进入swap流程
            swap(i, a);  //当前元素比前一个数字小，进入swap流程
            }
            System.out.println(Arrays.toString(a));
        }
        System.out.println(Arrays.toString(a));
    }

    public static void swap(int m, int[] arr) { //swap接收两个参数，一个是当前基数的下标，一个是数组对象本身
        int sw = arr[m];  //下面三行是把基数和前一个数字进行交换，基数变成前一个了，所以新的基数是在老的基数上自减一
        arr[m] = arr[m-1];
        arr[m-1] = sw;
        m -= 1;  //新的基数是在老的基数上自减一。如果下面的两个都不满足，方法到这里就结束了，数组对象已经是改过的了

        if (m==0) return;  //判断基数自减一后，是不是到第一位了，如果到第一位了，不用对比了，就跳出方法，return
        //因为操作的数组对象本身，所以不用返回什么值，数组对象已经改了

        if (arr[m] < arr[m-1]) {  //如果基数自减一后不是0，且基数还是比前面的小，就递归调用自己，知道满足跳出条件
            swap(m, arr);
        }

    }
}
